#include "Graph.h"

Graph::Graph(int NumOfVertex)
{
	if ( NumOfVertex <= 0 )
		throw BadNumberOfVertex();
	MAX_VERTS = NumOfVertex;

	mVertexList.reserve( MAX_VERTS );
	adjMat = new int*[MAX_VERTS];

	for (int j = 0; j < MAX_VERTS; j++) 
	{
		adjMat[j] = new int[MAX_VERTS];
		for (int k = 0; k < MAX_VERTS; k++) // matrix to 0
		{
			adjMat[j][k] = 0;
		}
	}
}
Graph::~Graph()
{
	for (int j = 0; j < MAX_VERTS; j++)
	{
		delete[] adjMat[j];
	}
	delete[] adjMat;
}
int Graph::searchVertexByLabel(string pLabel)
{
	for ( vertexListIterator i = mVertexList.begin(); i != mVertexList.end(); ++i )
	{
		if ( (*i).getLabel() == pLabel )
		{
			return int(i - mVertexList.begin());
		}
	}
	throw NoSuchVertex();
}
void Graph::addVertex(string pLabel)
{
	try
	{
		getVertex( pLabel );
		throw AttempDuplicateVertex();
	}
	catch ( NoSuchVertex )
	{
		mVertexList.push_back( Vertex(pLabel) );		
	}
}
void Graph::addEdge(string pStartVertex, string pEndVertex) 
{
	int posStartVertex	= searchVertexByLabel(pStartVertex);
	int posEndVertex	= searchVertexByLabel(pEndVertex);	

	adjMat[posStartVertex][posEndVertex] = 1;
	adjMat[posEndVertex][posStartVertex] = 1;
}
Vertex* Graph::getVertex(string pLabel)
{
	int position = searchVertexByLabel( pLabel );

	return &mVertexList.at( position );
}
Vertex* Graph::getVertex(int position)
{
	return &mVertexList.at( position );
}

bool Graph::getEdge(string pStartVertex, string pEndVertex)
{
	int posStartVertex	= searchVertexByLabel(pStartVertex);
	int posEndVertex	= searchVertexByLabel(pEndVertex);	

	if ( adjMat[posStartVertex][posEndVertex] == 1 && adjMat[posEndVertex][posStartVertex] == 1 )
	{
		return true;
	}
	return false;
}
int Graph::getAdjUnvisitedVertex(int position)
{
//	int position = searchVertexByLabel( pLabel );
	for (int j = 0; j != mVertexList.size(); ++j)
	{
		if ( adjMat[position][j] == 1 && !mVertexList.at(j).getWasVisited() )
			return j;
	}
	return -1;
}
void Graph::dfs(string pStartVertex, string pEndVertex) // depth-first search
{
	int positionStart = searchVertexByLabel( pStartVertex );
	int positionEnd = searchVertexByLabel( pEndVertex );
	mVertexList.at(positionStart).setWasVisited( true ); 
	theStack.push_front(positionStart); 
	while ( !theStack.empty() ) 
	{
		int v = getAdjUnvisitedVertex( theStack.front() );
		if (v == -1) // if no such vertex,
		{
			theStack.pop_front(); 
		}
		else
		{
			mVertexList.at(v).setWasVisited( true ); 
			theStack.push_front(v ); 
			if ( positionEnd == v )
				break;
		}
	}
}

void Graph::printAdjMatr()
{
	for (int i = 0; i < MAX_VERTS; ++i)
	{
		for (int j = 0; j < MAX_VERTS; ++j)
		{
			cout << adjMat[i][j] << " ";
		}
		cout << endl;
	}
}
void Graph::printStack()
{
	for (list<int>::iterator i = theStack.begin(); i != theStack.end(); ++i)
	{
		cout << (*i) << endl;
	}
}
